Cryptographic developments in the last decade have identified public key systems as very desirable from an operational viewpoint. In public key systems, data to be secured is encrypted with an enciphering key, and decrypted with a deciphering key that is different from and not computable from the enciphering key. In a major class of such public key encryption systems, such as the RSA (Rivest, Shamir, Adelman), Diffie-Hellman, and SEEK (Secure Electronic Exchange of Keys) methods, data to be secured (or a message coded in numeric form) B is enciphered using a public key (E,M) to obtain a ciphertext C, as follows: EQU C=B.sup.E (Modulo M)
In this operation, the ciphertext C is the remainder of B.sup.E when divided by M. As is preferred, all quantities are large integers which may be several hundred bits long, and M is the product of two large prime numbers p and q.
The deciphering operation to retrieve the data or message B is similar except that a private key (D,M) is used, as follows: EQU B=C.sup.D (Modulo M)
Here D depends on p and q, and it is extremely difficult to compute D from E and M as it is to factor M. As an example of the RSA method, the word "IT" can be encrypted using the numeric code representation for letters A=01, B=02, . . . Z=26, so that the word "IT" is represented by the number 0920. Then with M=47 * 59=2773, and E=17, the ciphertext C=920.sup.17 ; (Modulo 2773)=948. Using p=47 and q=59, a value D=157 can be derived as the private key by which the original message can be calculated as 948.sup.157 ; (Modulo 2773)=920, which is decoded as the word "IT".
Modular arithmetic plays a large part in public key encryption systems because it uses smooth and continuous functions to obtain discontinuous values which jump around in a haphazard way. While the encryption method may be known, the security of this form of cipher rests mainly in the difficulty, if not impossibility, of computing the enciphering or deciphering values. The code breaker's work increases much more rapidly with increasing length N of the numbers used than does the work of an authorized sender or receiver. For example, if the code breaking work is proportional to N.sup.N whereas the encrypting/decrypting work is proportional to N.sup.3, then doubling N from 10 to 20 makes an authorized user's work 8 times greater but the code breaker's work 4010 greater.
For further information regarding such public key systems and modular arithmetic encryption functions, reference is made to the article entitled "The Mathematics of Public Key Cryptography" by Martin Hellman, published in Scientific American Magazine, August 1979, Vol. 241, No. 2, pages 146 to 157.
A described above, using a public key for encryption and a secret key for description prevents a third party from extracting processed information from a communication system. But also, using a secret key for encryption ("signing a message") and a public key for decryption ("reading the signature") prevents a third party from inserting bogus information into a communication system.
The implementation of such public key encryption systems depends upon the ability to perform the mathematical modulo exponentiation function quickly and within given hardware constraints. Existing silicon-based circuit devices typically can perform a 512-bit computation in tens or hundreds of milliseconds (ms). The rather long computation time makes this encryption technique suitable only for key management and low-rate data applications. Such existing devices also exhibit severely degraded performance when they are cascaded to support a higher precision arithmetic. Furthermore, secure data transmission, a rapidly growing application, requires authentication of lengthy packets which could greatly increase the computation time. High data rate applications and real-time performance in image or voice communication systems would require at least a tenfold reduction in current exponentiation computation times in order to be feasible for implementation.